package com.heima.leetcode.datastructure.stack;

import com.heima.datastructure.stack.ArrayStack;

/**
 * <h3>括号匹配 20</h3>
 */
public class ParenthesisMatch {
    // 遍历字符串，如果遇到的是左括号，则把对应的右括号存入栈顶
    //            如果遇到的是右括号，则弹出栈顶元素比较
    // 如果遇到的右括号等于弹出的右括号，则继续遍历，如果遇到的
    // 右括号不等于弹出的右括号，返回false，直至遍历结束，若遍历
    // 结束后栈内还有元素没有被弹出，返回false，否则返回true

    /**
     * 判断给定的字符串中的括号是否匹配
     * @param string 字符串
     * @return 都匹配则返回true，否则false
     */
    public static boolean isValid(String string){
        ArrayStack<Character> stack = new ArrayStack<>(string.length());
        for (int i = 0; i < string.length(); i++) {
            char c = string.charAt(i);
            if (c == '('){
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            }
            if (c != ')' && c != ']' && c != '}'){
                continue;
            } else {
                if (stack.isEmpty() || c != stack.pop()){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
